package bgai.gamelogic;

import java.util.AbstractMap;
import java.util.AbstractMap.SimpleEntry;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.NavigableMap;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;

import bgai.ai.minimax.Board;
import bgai.ai.minimax.BoardType;
import bgai.ai.minimax.ChanceEvent;
import bgai.ai.minimax.Evaluator;
import bgai.ai.minimax.MoveEvent;
import bgai.players.Player;

/**
 * Classe principale contenente la logica di gioco di Backgammon: e' indipendente
 * dall'interfaccia utente utilizzata (es. GUI) e dal tipo di giocatore 
 * (es. giocatore umano o IA).
 * <p>
 * Utilizziamo la versione base delle regole di gioco: niente dado dei raddoppi
 * e un solo tipo di vittoria (vittoria semplice). I due giocatori sono identificati
 * come "giocatore White" e "giocatore Black".
 * <p>
 * NOTA BENE: il giocatore nero si muove in senso antiorario (decremento dell'indice
 * di posizione), mentre il giocatore bianco si muove in senso orario (incremento
 * dell'indice di posizione).
 * <p>
 * Riferimento per le regole: http://it.wikipedia.org/wiki/Regole_del_backgammon
 * <p>
 * Viene utilizzata la numerazione e la disposizione delle pedine cosi' come 
 * descritto in: http://en.wikipedia.org/wiki/Backgammon_notation
 * Pertanto:
 * <ul>
 * 		<li>la numerazione delle punte e' 1-24 (parte da 1, non da 0)
 * 		<li>la casa del nero e' [1-6]
 * 		<li>la casa del bianco e' [19-24]
 *  </ul>
 * Ricorda inoltre che:
 * <ul>
 * 		<li>i checker bianchi sulla bar entrano nella casa del nero, ovvero [1-6]
 * 		<li>i checker neri sulla bar entrano nella casa del bianco, ovvero [19-24] 
 * </ul>
 * Il valore speciale {@link #BAR} indica
 * che la pedina e' entrata dalla bar, mentre il valore {@link #OFF} indica un movimento 
 * fuori dalla tavola (bear off). Questa numerazione e' statica, nel senso che 
 * non cambia a seconda del turno del giocatore (ad esempio il point di indice
 * 1 durante il turno del giocatore nero non diventa il point di indice 24 durante
 * il turno del giocatore bianco).
 */
public class Backgammon implements Iterable<Point>, Cloneable, Board {
	/**
	 * Numero di checker per ogni giocatorre
	 */
	public static final int NUM_CHECKERS = 15;
	/**
	 * Numero di point nella board
	 */
	public static final int NUM_POINTS = 24;
	/**
	 * Indice del bar, indipendentemente che sia del giocatore bianco o nero
	 */
	public static final int BAR=-1;
	
	/**
	 * Indice per un movimento fuori dal tavolo, ovvero un bear off, 
	 * indipendentemente che sia del giocatore bianco o nero 
	 */
	public static final int OFF=-2;
	
	/**
	 * Struttura dati per lo stato della tavola di gioco.
	 * <p>
	 * Per la numerazione delle punte (points) fare riferimento a:
	 * http://en.wikipedia.org/wiki/Backgammon_notation
	 */
	private Point[] board= new Point[24];
	/**
	 * Pedine del giocatore White che sono sulla barra, ovvero sono state mangiate.
	 */
	private int barCheckersWhite;
	/**
	 * Pedine del giocatore Black che sono sulla barra, ovvero sono state mangiate.
	 */
	private int barCheckersBlack;
	/**
	 * Pedine che il giocatore White e' riuscito a portare fuori dalla tavola.
	 */
	private int borneOffCheckersWhite;
	/**
	 * Pedine che il giocatore Black e' riuscito a portare fuori dalla tavola.
	 */
	private int borneOffCheckersBlack;
	
	/**
	 * Colore del giocatore che ha il turno attuale.
	 */
	private CheckerColor turn;
	
	/**
	 * Giocatore che ha il primo turno
	 */
	private CheckerColor firstTurn;
	
	/**
	 * Conteggio dei turni
	 */
	private int turnNum;
	
	/**
	 * Player nero (umano o AI)
	 */
	private Player blackPlayer;
	
	/**
	 * Player bianco (umano o AI)
	 */
	private Player whitePlayer;
	
	/**
	 * Clone usato per le mosse parziali: contiene un riferimento ad una copia
	 * stabile dello stato.
	 */
	private Backgammon stableState;
	
	/**
	 * Tiro di dadi (al momento usato solo per minimax
	 */
	private Roll roll;
	/**
	 * Generatore di numeri casuali per i dadi
	 */
	private Random rand;
	
	/**
	 * Tipo del nodo attuale
	 */
	private BoardType nodeType;
	
	/**
	 * se true non stampa niente su stdout
	 */
	private boolean silent;
	
	/**
	 * Crea una nuova tavola da gioco disponendo le pedine nella loro posizione
	 * iniziale
	 */
	public Backgammon(Player player1, Player player2, long seed) {
		if (
				( player1.getColor().isBlack() && player2.getColor().isBlack() ) ||
				( player1.getColor().isWhite() && player2.getColor().isWhite() )
				) {
			
			throw new BackgammonError(this, "Player dello stesso colore");
			
		} else if (player1.getColor().isBlack()) {
			
			this.blackPlayer= player1;
			this.whitePlayer= player2;
			
		} else {
			
			this.blackPlayer= player2;
			this.whitePlayer= player1;
			
		}
		
		roll= null;
		rand= new Random(seed);
		init();
		//initDance();
		//initBearOff();
		//initBearOff2();
		//initBearOff3();
		//initHit();
	}
	
	/**
	 * Ripristina la configurazione iniziale
	 */
	private void init() {
		barCheckersBlack= 0;
		barCheckersWhite= 0;
		borneOffCheckersBlack= 0;
		borneOffCheckersWhite= 0;
		turn=null;
		
		for (int k=0; k<board.length; k++) {
			board[k]= new Point(k+1);
		}
		board[ 1 -1]= new Point(1, CheckerColor.WHITE, 2);
		board[ 6 -1]= new Point(6, CheckerColor.BLACK, 5);
		board[ 8 -1]= new Point(8, CheckerColor.BLACK, 3);
		board[12 -1]= new Point(12, CheckerColor.WHITE, 5);
		board[13 -1]= new Point(13, CheckerColor.BLACK, 5);
		board[17 -1]= new Point(17, CheckerColor.WHITE, 3);
		board[19 -1]= new Point(19, CheckerColor.WHITE, 5);
		board[24 -1]= new Point(24, CheckerColor.BLACK, 2);
		
		stableState= null;
		stableState= (Backgammon) this.clone();
	}

	
	/**
	 * Configurazione in cui il nero balla
	 */
	@SuppressWarnings("unused")
	private void initDance() {
		barCheckersBlack= 0;
		barCheckersWhite= 0;
		borneOffCheckersBlack= 0;
		borneOffCheckersWhite= 0;
		turn=null;
		
		for (int k=0; k<board.length; k++) {
			board[k]= new Point(k+1);
		}

		board[ 1 -1]= new Point(1, CheckerColor.BLACK, 5);
		board[ 6 -1]= new Point(6, CheckerColor.BLACK, 5);
		
		// casa bianco: [19-24]
		board[19 -1]= new Point(19, CheckerColor.WHITE, 3);
		board[20 -1]= new Point(20, CheckerColor.WHITE, 3);
		board[21 -1]= new Point(21, CheckerColor.WHITE, 3);
		board[22 -1]= new Point(22, CheckerColor.WHITE, 2);
		board[23 -1]= new Point(23, CheckerColor.WHITE, 2);
		board[24 -1]= new Point(24, CheckerColor.WHITE, 2);
		
		barCheckersBlack= 5;
		
		stableState= null;
		stableState= (Backgammon) this.clone();
	}
	
	/**
	 * Configurazione per fare subito bear off
	 */
	@SuppressWarnings("unused")
	private void initBearOff() {
		barCheckersBlack= 0;
		barCheckersWhite= 0;
		borneOffCheckersBlack= 0;
		borneOffCheckersWhite= 0;
		turn=null;
		
		for (int k=0; k<board.length; k++) {
			board[k]= new Point(k+1);
		}
		board[ 1 -1]= new Point(1, CheckerColor.BLACK, 2);
		board[ 6 -1]= new Point(6, CheckerColor.BLACK, 5);
		board[19 -1]= new Point(19, CheckerColor.WHITE, 5);
		board[24 -1]= new Point(24, CheckerColor.WHITE, 2);

		borneOffCheckersBlack= 8;
		borneOffCheckersWhite= 8;
		
		stableState= null;
		stableState= (Backgammon) this.clone();
	}
	@SuppressWarnings("unused")
	private void initBearOff2() {
		barCheckersBlack= 0;
		barCheckersWhite= 0;
		borneOffCheckersBlack= 0;
		borneOffCheckersWhite= 0;
		turn=null;
		
		for (int k=0; k<board.length; k++) {
			board[k]= new Point(k+1);
		}
		board[ 1 -1]= new Point(1, CheckerColor.BLACK, 5);
		board[ 5 -1]= new Point(5, CheckerColor.BLACK, 5);
		board[ 6 -1]= new Point(6, CheckerColor.BLACK, 5);
		
		board[23 -1]= new Point(23, CheckerColor.WHITE, 1);
		board[24 -1]= new Point(24, CheckerColor.WHITE, 1);

		borneOffCheckersWhite= 13;
		
		stableState= null;
		stableState= (Backgammon) this.clone();
	}
	
	@SuppressWarnings("unused")
	private void initBearOff3() {
		barCheckersBlack= 0;
		barCheckersWhite= 0;
		borneOffCheckersBlack= 0;
		borneOffCheckersWhite= 0;
		turn=null;
		
		for (int k=0; k<board.length; k++) {
			board[k]= new Point(k+1);
		}
		board[ 1 -1]= new Point(1, CheckerColor.BLACK, 6);
		board[ 5 -1]= new Point(5, CheckerColor.BLACK, 8);
		board[ 6 -1]= new Point(6, CheckerColor.BLACK, 1);
		
		board[22 -1]= new Point(22, CheckerColor.WHITE, 5);
		board[23 -1]= new Point(23, CheckerColor.WHITE, 5);
		board[24 -1]= new Point(24, CheckerColor.WHITE, 5);

		stableState= null;
		stableState= (Backgammon) this.clone();
	}

	/**
	 * Configurazione con dei checker sulla bar
	 */
	@SuppressWarnings("unused")
	private void initFromBar() {
		barCheckersBlack= 8;
		barCheckersWhite= 8;
		borneOffCheckersBlack= 0;
		borneOffCheckersWhite= 0;
		turn=null;
		
		for (int k=0; k<board.length; k++) {
			board[k]= new Point(k+1);
		}
		board[ 1 -1]= new Point(1, CheckerColor.WHITE, 2);
		board[ 6 -1]= new Point(6, CheckerColor.WHITE, 5);
		board[19 -1]= new Point(19, CheckerColor.BLACK, 5);
		board[24 -1]= new Point(24, CheckerColor.BLACK, 2);
		
		stableState= null;
		stableState= (Backgammon) this.clone();
	}
	
	/**
	 * Configurazione con elevata probabilita' di mangiare
	 */
	@SuppressWarnings("unused")
	private void initHit() {
		barCheckersBlack= 0;
		barCheckersWhite= 0;
		borneOffCheckersBlack= 0;
		borneOffCheckersWhite= 0;
		turn=null;
		
		for (int k=0; k<board.length; k++) {
			board[k]= new Point(k+1);
		}
		board[ 1 -1]= new Point(1, CheckerColor.WHITE, 1);
		board[ 2 -1]= new Point(2, CheckerColor.WHITE, 1);
		board[ 3 -1]= new Point(3, CheckerColor.WHITE, 1);
		board[ 4 -1]= new Point(4, CheckerColor.BLACK, 1);
		board[ 5 -1]= new Point(5, CheckerColor.BLACK, 1);
		board[ 6 -1]= new Point(6, CheckerColor.BLACK, 1);
		
		board[ 7 -1]= new Point(7, CheckerColor.WHITE, 1);
		board[ 8 -1]= new Point(8, CheckerColor.WHITE, 1);
		board[ 9 -1]= new Point(9, CheckerColor.WHITE, 1);
		board[10 -1]= new Point(10, CheckerColor.BLACK, 1);
		board[11 -1]= new Point(11, CheckerColor.BLACK, 1);
		board[12 -1]= new Point(12, CheckerColor.BLACK, 4);

		board[13 -1]= new Point(13, CheckerColor.WHITE, 4);
		board[14 -1]= new Point(14, CheckerColor.WHITE, 1);
		board[15 -1]= new Point(15, CheckerColor.WHITE, 1);
		board[16 -1]= new Point(16, CheckerColor.BLACK, 1);
		board[17 -1]= new Point(17, CheckerColor.BLACK, 1);
		board[18 -1]= new Point(18, CheckerColor.BLACK, 1);

		board[19 -1]= new Point(19, CheckerColor.WHITE, 1);
		board[20 -1]= new Point(20, CheckerColor.WHITE, 1);
		board[21 -1]= new Point(21, CheckerColor.WHITE, 1);
		board[22 -1]= new Point(22, CheckerColor.BLACK, 1);
		board[23 -1]= new Point(23, CheckerColor.BLACK, 1);
		board[24 -1]= new Point(24, CheckerColor.BLACK, 1);

		stableState= null;
		stableState= (Backgammon) this.clone();
	}

	/// METODI PER LE MOSSE

	/**
	 * Restituisce true se la posizione data e' valida, ovvero se e' compreso
	 * nell'intervallo [1-24] (in questo caso si tratta di un checker su un 
	 * point) oppure e' uno dei valori speciali {@link #BAR} o {@link #OFF}.
	 * Nota che non tiene conto dello stato della tavola.
	 * @param position posizione da validare
	 * @return true se la posizione e' valida
	 */
	public static boolean checkPosition(int position) {
		if (isOnTable(position) || isBar(position) || isOff(position)) return true;
		else return false;
	}

	/**
	 * Restituisce true se la posizione data corrisponde alla bar
	 * @param pos posizione da verificare
	 * @return vedi descrizione
	 */
	public static boolean isBar(int pos) {
		return (pos==BAR);
	}
	

	/**
	 * Restituisce true se la posizione data corrisponde ad un bear off
	 * @param pos posizione da verificare
	 * @return vedi descrizione
	 */
	public static boolean isOff(int pos) {
		return (pos==OFF);
	}
	

	/**
	 * Restituisce true se la posizione data corrisponde all'indice di un point
	 * @param pos posizione da verificare
	 * @return vedi descrizione
	 */
	public static boolean isOnTable(int pos) {
		if (1<=pos && pos<=NUM_POINTS) return true;
		else return false;
	}
	
	/**
	 * Restituisce true se la posizione data e' una posizione iniziale valida 
	 * per il giocatore che ha attualmente il turno, ovvero se e' compreso
	 * nell'intervallo [1-24] (in questo caso verifica se ci sono checker su quel
	 * point e se non ci sono checker sulla bar) oppure e' il valore speciale 
	 * {@link #BAR} (in questo caso verifica se ci sono checker sulla bar).
	 * @param startPos posizione da validare
	 * @return true se la posizione e' valida
	 */
	public boolean checkStartingPosition(int startPos) {
		if (checkPosition(startPos)) {
			
			if (isBar(startPos)) {
				
				if (getBarCheckers(turn)>0) return true;
				else return false;
				
			} else if (isOnTable(startPos)) {
				
				// partenza da un point generico
				Point p= getPoint(startPos);
				// 1) su questo point sono presenti dei checker del colore del giocatore di turno
				// 2) non ci sono checker sulla bar
				if (p.getNum()>0 && p.getColor().equals(turn) && !isEnterPhase()) {
					return true;
				} else {
					return false;
				}

			} else {
				
				// startPos==OFF
				return false;
				
			}
			
		} else {
			return false;
		}
	}
	

	/**
	 * Restituisce true se, per il giocatore che ha attualmente il turno,
	 * la posizione data e' una posizione finale valida. 
	 * Il checker puo' muoversi nella posizione
	 * finale se:
	 * <ul>
	 * 		<li>NON sono presenti due o piu' checker di colore diverso.
	 * 		<li>in caso di bear off il gioco deve essere nella fase di end game
	 * </ul>
	 * @param endPos posizione da validare
	 * @param color colore del checker di cui si sta vacendo la validazione
	 * @return true se la posizione e' valida
	 * @see #isEndGamePhase()
	 */
	public boolean checkEndingPosition(int endPos) {
		if (checkPosition(endPos)) {
			if (isOff(endPos)) {
				// bear off, ma sono davvero nella fase di end game?
				return isEndGamePhase();
			} else if (isOnTable(endPos)) {
				// arrivo su un point generico
				Point p= getPoint(endPos);
				// non posso andare in quel point se ci sono piu' di un checker di colore diverso
				return !isBusy(p); // se' e' occupata, la posizione non e' valida
			} else {
				// endPos==BAR
				return false;
			}
		} else {
			return false;
		}
	}
	
	/**
	 * Restituisce true se la posizione e' occupata da 2 o piu' checker di
	 * colore diverso a quello del giocatore attuale
	 * @param point
	 * @return
	 */
	public boolean isBusy(Point point) {
		// non posso andare in quel point se ci sono piu' di un checker di colore diverso
		if (point.getNum()>1 && !point.getColor().equals(turn)) {
			return true;
		} else {
			return false;
		}
	}
	
	/**
	 * Restituisce true se movendo il checker del giocatore attuale nel point dato,
	 * viene mangiato un checker avversario 
	 * @param point punto di destinazione
	 * @return se il giocatore di turno otterrebbe un hit
	 */
	public boolean isHit(Point point) {
		// e' presente un solo checker del colore avversario
		if (point.getNum()==1 && !point.getColor().equals(turn)) {
			return true;
		} else {
			return false;
		}
 	}
	
	/**
	 * Restituisce true se movendo il checker del giocatore attuale nel point dato,
	 * viene mangiato un checker avversario 
	 * @param point punto di destinazione
	 * @return se il giocatore di turno otterrebbe un hit
	 */
	public boolean isHit(int point) {
		return isHit(getPoint(point));
 	}
	
	/**
	 * Restituisce true se il giocatore corrente e' nella fase "end game",
	 * ovvero ha tutti i checker nella home board
	 * @return vedi descrizione
	 */
	public boolean isEndGamePhase() {
		if (turn.isBlack()) {
			// home board in [1-6]
			for (int k=7; k<=24; k++) {
				Point p= getPoint(k);
				if (p.getNum()>0 && p.getColor().isBlack()) {
					// ho trovato checker neri fuori home board!
					return false;
				}
			}
			return true;
		} else {
			// home board in [19-24]
			for (int k=1; k<=18; k++) {
				Point p= getPoint(k);
				if (p.getNum()>0 && p.getColor().isWhite()) {
					// ho trovato checker bianchi fuori home board!
					return false;
				}
			}
			return true;
		}
	}
	
	/**
	 * Restituisce true se il giocatore attuale ha checker sulla bar
	 * @return
	 */
	public boolean isEnterPhase() {
		if (turn.isBlack()) {
			return (barCheckersBlack>0);
		} else {
			return (barCheckersWhite>0);
		}
	}
	
	/**
	 * Espande il risultato di un lancio di dadi.
	 * Ad esempio se i dadi sono 3 e 5, restituisce <3,5>. Mentre se i dadi
	 * sono 4 e 4, restituisce <4,4,4,4>. Nota che non vengono cosiderati i
	 * risultati di combinazioni di piu' dadi. Ad esempio se i dadi sono 3 e 5,
	 * viene restituito solo <3,5> e non <3,5,8>.
	 * @param dice1 un dado
	 * @param dice2 l'altro dado
	 * @return vedi descrizione 
	 */
	private static List<Integer> expandDices(int dice1, int dice2) {
		Vector<Integer> dices= new Vector<Integer>();
		
		if (!checkDice(dice1, dice2)) {
			throw new DiceException(dice1, dice2);
		}
		
		if (dice2>dice1) {
			// ordino i dadi
			int h= dice1;
			dice1= dice2;
			dice2= h;
		}
		
		if (dice1==dice2) {
			// risultato doppio
			for (int k=0; k<4; k++) {
				dices.add(dice1);
			}
		} else {
			// dadi diversi
			dices.add(dice1);
			dices.add(dice2);
		}
		return dices;
	}

	/**
	 * Restituisce la posizione in cui un checker del giocatore attuale si muoverebbe. Tiene conto del
	 * fatto che il nero muove in senso antiorario (decremento indice) e il 
	 * bianco in senso orario (incremento indice).
	 * Nota che non controlla se la posizione iniziale o finale e' valida o meno
	 * @param startPos point di partenza
	 * @param points numero di point di movimento (deve essere {@code points>0}) 
	 * @return indice del point in cui si puo' spostare il checker, {@link #OFF} in caso di bear off
	 * @throws PositionException posizione di partenza non valida
	 * @throes DiceException se {@code points<1}
	 */
	private int calculateEndingPosition(int startPos, int points) throws PositionException, DiceException {

		if (!checkPosition(startPos)) {
			throw new PositionException(startPos, "Posizione di partenza non valida");
		} else if (points<1) {
			throw new DiceException(points, "Il numero di point di movimento deve essere maggiore o uguale a 1");
		} else {
			// posizione di partenza valida
			
			int dest;
			
			if (turn.equals(CheckerColor.BLACK)) {
				// antiorario => decremento

				if (startPos==BAR) dest=NUM_POINTS+1 - points;
				else dest= startPos - points;
				
				if (dest<1) dest= OFF;
			} else {
				// orario => incremento

				if (startPos==BAR) dest= points;
				else dest= startPos + points;
				
				if (dest>NUM_POINTS) dest= OFF;
			}
			
			return dest;
		}
	}
	
	/**
	 * Calcola la distanza effettiva (numero di point) fra una posizione e il 
	 * bear off
	 * @param pos posizione di partenza (non puo' essere {@link #BAR})
	 * @param col colore del checker
	 * @return distanza dal bear off
	 */
	public static int bearOffDistance(int pos, CheckerColor col) {
		if (!checkPosition(pos) || pos==BAR) {
			throw new PositionException(pos, "Non puoi calcolare la distanza di bear off da questa posizione");
		}
		int offDist; // distanza effettiva dal bear off
		if (col.isBlack()) {
			offDist= pos;
		} else {
			offDist= NUM_POINTS+1 - pos;
		}
		return offDist;
	}
	
	/**
	 * Esegue una singola mossa modificando la struttura dati
	 * @param startPoint posizione di partenza
	 * @param dice risultato del dado
	 * @return true se e' stato mangiato un checker avversario
	 * @throws PositionException la posizione di partenza non e' valida
	 * @throws BadMoveException non e' fare la mossa voluta
	 */
	private boolean singleMove(int startPos, int dice) throws BadMoveException {
		boolean hit=false;
		
		if (!checkStartingPosition(startPos)) {
			PositionException pe= new PositionException(startPos, "Posizione di partenza non valida");
			throw new BadMoveException(pe);
		}
		if (!checkDice(dice)) {
			throw new DiceException(dice, "Dado non valido");
		}
		int endPos= calculateEndingPosition(startPos, dice);
		if (!checkEndingPosition(endPos)) {
			PositionException pe= new PositionException(endPos, "Posizione di arrivo non valida");
			throw new BadMoveException(pe);
		}
		
		if (isOff(endPos)) {
			/*
			 * In caso di bear off ho gia' controllato di essere nella fase end game.
			 * Tuttavia posso fare bear off solo se il dado corrisponde esattamente
			 * al numero di point che servono per uscire OPPURE se il checker che 
			 * si sta movendo e' "l'ultimo"
			 */
			
			int offDist= bearOffDistance(startPos, turn); // distanza effettiva dal bear off
			
			if (dice>offDist) {
				/*
				 * Verifico che questo sia "l'ultimo" checker, ovvero verifico
				 * se esiste almeno un altro checker dello stesso colore che lo
				 * precede.
				 */
				if (turn.isBlack()) {
					// la casa del nero e' in [1-6]
					for (int k=6; k>startPos; k--) {
						Point p= getPoint(k);
						if (p.getNum()>0 && p.getColor().isBlack()) {
							// trovati checker neri
							throw new BadMoveException("Bear off non valido");
						}
					}
				} else {
					//  la casa del bianco e' [19-24]
					for (int k=19; k<startPos; k++) {
						Point p= getPoint(k);
						if (p.getNum()>0 && p.getColor().isWhite()) {
							// trovati checker bianchi
							throw new BadMoveException("Bear off non valido");
						}
					}
				}
			}
		}
		
		if (isBar(startPos)) {
			if (turn.isBlack()) barCheckersBlack--;
			else barCheckersWhite--;
		} else {
			try {
				getPoint(startPos).moveOut();
			} catch (PointException e) {
				throw new BadMoveException(e);
			}
		}
		if (isOff(endPos)) {
			if (turn.isBlack()) borneOffCheckersBlack++;
			else borneOffCheckersWhite++;
		} else {
			if (isHit(endPos)) {
				// checker avversario mangiato
				hit= true;
				if (turn.isBlack()) barCheckersWhite++;
				else barCheckersBlack++;
			}
			try {
				getPoint(endPos).moveIn(turn);
			} catch (PointException e) {
				throw new BadMoveException(e);
			}
		}
		return hit;
	}
	
	/**
	 * Verifica che {@code dices} sia un possibile sottoinsieme della lista
	 * restituita da {@link #expandDices(int, int)}. Ovverro verifica che:
	 * <ul>
	 * 		<li>la lista abbia fra 0 e 4 elementi
	 * 		<li>ogni elemento sia nell'intervallo [1-6]
	 * </ul> 
	 * @param dices dadi da verificare
	 * @return true se la lista e' corretta, false altrimenti
	 */
	private boolean checkDices(List<Integer> dices) {

		if (dices.size()<0 || dices.size()>4) {
			// numero impossibile di dadi
			return false;
		}
		
		// controllo che siano fra 1 e 6
		for (Integer m : dices) {
			if (!checkDice(m)) return false;
		}
		
		if (dices.size()>2) {
			/*
			 * Se size==2 possono essere due dadi uguali o diversi 
			 * (es: <3,5>, <4,4,4>, <4,4>).
			 * 
			 * Se size>2 allora sono tutti numeri uguali (e' stato lanciato un doppio)
			 */
			
			// verifico se i dadi sono veramente tutti uguali
			int first=-1;
			for (Integer m : dices) {
				if (first==-1) first= m;
				
				if (m!=first) {
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * Restituisce true se, dopo aver compiuto le mosse date, non e' piu' possibile
	 * compiere alcuna ulteriore mossa.
	 * @param moves mosse fatte finora
	 * @return vedi descrizione
	 * @throws BadMoveException se {@code moves} non e' valido 
	 */
	public boolean noLegalPositions(Move moves) throws BadMoveException {

		
		// verifico se ci sono mosse legali partendo dalla bar
		try {
			if (!legalPositions(BAR, moves).isEmpty()) {
				// ci sono delle mosse
				return false;
			}
		} catch (PositionException e) {
			// la bar era gia' vuota o lo e' diventata a seguito della simulazione: nessuna mossa legale
		}
		
		for (int k=1; k<=NUM_POINTS; k++) {
			try {
				// verifico se ci sono posizioni legali partendo dal point "k"
				if (!legalPositions(k, moves).isEmpty()) {
					// ci sono delle mosse
					return false;
				}
			} catch (PositionException e) {
				// il point era gia' vuoto o lo e' diventato a seguito della simulazione: nessuna mossa legale
			}
		}
		return true; // nessuna mossa legale
	}
	
	/**
	 * Restituisce true se il giocatore attuale non puo' fare alcun tipo di mossa
	 * @param dice1 un dado
	 * @param dice2 l'altro dado
	 * @return true se non puo' fare alcuna mossa, false almeno un checker puo' muoversi
	 * @throws DiceException dadi non validi
	 */
	public boolean noLegalPositions(int dice1, int dice2) throws DiceException {
		if (!checkDice(dice1, dice2)) {
			throw new DiceException(dice1, dice2, "Dadi non validi");
		}
		Move moves= new Move(dice1, dice2, turn);
		try {
			return noLegalPositions(moves);
		} catch (BadMoveException e) {
			throw new BackgammonError(this, "Eccezione in noLegalPositions(int,int): no sarebbe dovuto accadere perche' non e' ancora stata fatta alcuna mossa", e);
		}
	}
	
	/**
	 * Restituisce true se, dopo aver effettuato la mossa data, non e' possibile
	 * muovere il checker. Restituisce true anche nel caso in cui la posizione
	 * rimanga vuota.
	 * @param currentPoint posizione di partenza del checker
	 * @param moves mosse fatte finora
	 * @return vedi descrizione
	 * @throws BadMoveException moves non e' un insieme di mosse legale
	 */
	public boolean noLegalPositions(int currentPoint, Move moves) throws DiceException, BadMoveException {
		
		try {
			if (legalPositions(currentPoint, moves).isEmpty()) {
				return true;
			} else {
				return false;
			}
		} catch (PositionException e) {
			// la posizione era gia' vuota o lo e' diventata a seguito della simulazione: nessuna mossa legale
			return true;
		}
		
	}
	
	/**
	 * Data la posizione di un checker del giocatorre attuale, restituisce la lista delle posizioni
	 * in cui tale checker puo' muoversi.
	 * <p>
	 * NOTA BENE:
	 * <ul>
	 * 		<li>il giocatore nero si muove in senso antiorario, mentre il giocatore
	 * 		bianco si muove in senso orario.
	 * 		<li>la lista delle mosse deve essere un sottoinsieme di {@link #expandDices(int, int)}
	 * </ul>
	 * @param currentPoint point di partenza del checker
	 * @param dices lista delle possibili mosse (esempi: <3,5>, <3>, <4,4,4>). Deve avere almeno al massimo 4 elementi
	 * @return indici dei point in cui tale checker puo' muoversi, un insieme vuoto se non ci sono posizioni in cui puo' muoversi
	 * @throws PositionException la posizione di partenza non e' valida
	 * @throws BadMoveException moves non e' un insieme di mosse legale
	 */
	public Set<Integer> legalPositions(int currentPoint, Move moves) throws PositionException, BadMoveException {
		
		// NB: NERO   => decrementa
		//     BIANCO => incrementa
		
		// dadi ancora da usare
		List<Integer> dices= new LinkedList<Integer>();
		dices.addAll(expandDices(moves.getHighDice(), moves.getLowDice()));
		if (moves.getUsedDices().size()>4) throw new BackgammonError(this, "Troppe mosse: "+moves);
		for (Integer i : moves.getUsedDices()) {
			dices.remove(i);
		}
		
		// CONTROLLI VARI PRIMA DI INIZIARE

		Backgammon bg= (Backgammon) stableState.clone(); // questa variabile la usero' anche dopo
		Move movesCl= (Move) moves.clone();
		movesCl.clearHit();
		bg.forceMove(movesCl); // simulo le mosse fatte finora

		if (!bg.checkStartingPosition(currentPoint)) {
			// posizione iniziale non valida
			throw new PositionException(currentPoint, "Posizione iniziale non valida");
		}
		
		// ORA POSSO INIZIARE
				
		Set<Integer> legalPoints= new HashSet<Integer>(); // tutte le combinazioni ottenibili da dices
		
		// vado per casi
		if (dices.isEmpty()) {

			return legalPoints; // restituisco un set vuoto
		
		} else if (dices.size()==1 || dices.size()>2) {
						
			// se size>2 allora tutti i dadi sono uguali
			legalPoints.addAll(bg.legalPosHelper(currentPoint, dices));
			
		} else {
			
			// size==2
			
			// costruisco due liste di due elementi che differiscono solo per l'ordine
			
			List<Integer> moves1= new LinkedList<Integer>();
			List<Integer> moves2= new LinkedList<Integer>();
			
			int dice1= dices.get(0);
			int dice2= dices.get(1);
			
			moves1.add(dice1);
			moves1.add(dice2);
			
			moves2.add(dice2);
			moves2.add(dice1);
			
			// calcolo le mosse
						
			legalPoints.addAll(bg.legalPosHelper(currentPoint, moves1));
			legalPoints.addAll(bg.legalPosHelper(currentPoint, moves2));
			
		}
		
		return legalPoints;
	}
	
	/**
	 * Simula le mosse date partenddo da un posizione iniziale. Restituisce 
	 * l'insieme delle posizioni toccate.
	 * <p>
	 * Non effettua il controllo dei parametri
	 * @param currentPoint posizione  corrente
	 * @param moves lista ordinata di mosse da provare
	 * @return vedi descrizione
	 * @throws PositionException posizione iniziale non valida
	 */
	private Set<Integer> legalPosHelper(int currentPoint, List<Integer> moves) {
		// NB: NERO   => decrementa
		//     BIANCO => incrementa
		
		Set<Integer> legalPoints= new HashSet<Integer>();
		
		Backgammon bg= (Backgammon) this.clone();
		
		try {
			int curPos= currentPoint;
			for (Integer m : moves) {
				int endPos= bg.calculateEndingPosition(curPos, m);
				bg.singleMove(curPos, m);
				curPos= endPos;
				legalPoints.add(endPos); // la posizione finale e' legale
				
				// bear off: mi fermo
				if (isOff(endPos)) break;
				
				// se currentPoint==BAR e con >=2 checker sulla bar, bisogna svuotare la bar prima di muovere oltre
				if (!bg.checkStartingPosition(curPos)) break;
			}
		} catch (BadMoveException e) {
			// appena trovo una mossa illegale mi fermo: non devo propagare l'eccezione
		}
		
		return legalPoints;
	}
	
	/**
	 * Data una posizione iniziale e finale, genera una instanza di {@link CheckerMove}
	 * che rappresenta tale mossa
	 * @param startPos posizione iniziale
	 * @param endPos posizione finale
	 * @param moves mosse fatte finora
	 * @return la mossa
	 * @throws BadMoveException la mossa desiderata non e' legale
	 */
	public CheckerMove generateCheckerMove(int startPos, int endPos, Move moves) throws BadMoveException {

		// dadi ancora da usare
		List<Integer> dices= new LinkedList<Integer>();
		dices.addAll(expandDices(moves.getHighDice(), moves.getLowDice()));
		for (Integer i : moves.getUsedDices()) {
			dices.remove(i);
		}
		
		CheckerMove chkMove;
		
		if (dices.size()==0) {
			
			// niente da fare
			chkMove= new CheckerMove(turn);
			
		} else if (dices.size()==1 || dices.size()>2) {
			
			// se size>2 allora tutti i dadi sono uguali
			
			chkMove= generateCheckerMove(startPos, endPos, dices);
			
		} else {
			
			// size==2

			// costruisco due liste di due elementi che differiscono solo per l'ordine
			
			List<Integer> moves1= new LinkedList<Integer>();
			List<Integer> moves2= new LinkedList<Integer>();
			
			int dice1= dices.get(0);
			int dice2= dices.get(1);
			
			moves1.add(dice1);
			moves1.add(dice2);
			
			moves2.add(dice2);
			moves2.add(dice1);
			
			try {
				chkMove= generateCheckerMove(startPos, endPos, moves1);
			} catch (BadMoveException e) {
				chkMove= generateCheckerMove(startPos, endPos, moves2);
			}
			
		}
		
		return chkMove;
		
	}
	
	/**
	 * Data una posizione iniziale e finale, genera una instanza di {@link CheckerMove}
	 * che rappresenta tale mossa utilizzando una specifica sequenza di dadi
	 * @param startPos posizione iniziale
	 * @param endPos posizione finale
	 * @param moves lista ordinata di dadi da usare
	 * @return la mossa
	 * @throws BadMoveException la mossa desiderata non e' legale o non e' realizzabile
	 */
	private CheckerMove generateCheckerMove(int startPos, int endPos, List<Integer> moves) throws BadMoveException {
		
		CheckerMove chkMove= new CheckerMove(turn);
		Backgammon bg= (Backgammon) this.clone();
		int curPos= startPos;
		
		for (Integer d : moves) {
			
			int dest= bg.calculateEndingPosition(curPos, d);
			boolean hit= bg.singleMove(curPos, d);
			
			SingleMove sm= new SingleMove(curPos, dest, d, turn);
			sm.setHit(hit);
			chkMove.add(sm);
			
			curPos= dest;
			
			if (curPos==endPos) break; // raggiunto la posizione bersaglio
			
			if (isOff(curPos)) break; // ho fatto bear off senza toccare la posizione bersaglio
		}
		
		if (curPos==endPos) {
			return chkMove;
		} else {
			throw new BadMoveException(chkMove, "Impossibile arrivare alla posizione di destinazione: "+endPos);
		}
		
	}
	
	/**
	 * Ripristina lo stato a quello immediatamente dopo l'ultima chiamat a 
	 * {@link #move(Move)} 
	 */
	public void restore() {
		// il ripristino non deve ricreare le istanze di Point, ma solo modificarle
		for (Point p : board) {
			int num= p.getPosition();
			p.copy(stableState.getPoint(num));
		}
		
		// altri campi
		barCheckersBlack= stableState.barCheckersBlack;
		barCheckersWhite= stableState.barCheckersWhite;
		borneOffCheckersBlack= stableState.borneOffCheckersBlack;
		borneOffCheckersWhite= stableState.borneOffCheckersWhite;
		turn= stableState.turn;
	}
	
	/**
	 * Usato per player umano
	 * <p>
	 * Esegue una singola azione parziale modificando la struttura dati.
	 * @param chkMove mossa
	 * @throws BadMoveException se la mossa e' illegale. IMPORTANTE: causa uno 
	 * stato non coerente. Per ripristinare uno stato coerente usare {@link #restore()}
	 */
	public void partialMove(CheckerMove chkMove) throws BadMoveException {
		if (!silent) System.out.println("Esecuzione mossa parziale: " + chkMove);
		// eseguo le mosse: modifico la struttura dati
		// muovo fuori la posizione iniziale e dentro quella finale
		for (SingleMove sing : chkMove) {

			int startPos= sing.getStartingPosition();
			int dice= sing.getDice();
			
			int dest= calculateEndingPosition(startPos, dice);
			boolean hit= singleMove(startPos, dice);
			
			if (dest!=sing.getEndingPosition()) {
				throw new BadMoveException(chkMove, "La posizione finale in SingleMove non e' corretta: sarebbe dovuta essere "+dest+" ma invece e' "+sing.getEndingPosition());
			}

			if (hit!=sing.isHit()) {
				// flag non correttamente settato
				throw new BadMoveException(chkMove, "Flag hit non corretto in "+sing+", sarebbe dovuto essere "+hit);
			}
		}
	}
	
	/**
	 * Usato per player computer
	 * <p>
	 * Esegue una singola azione parziale modificando la struttura dati.
	 * @param singMove mossa
	 * @throws BadMoveException se la mossa e' illegale. IMPORTANTE: causa uno 
	 * stato non coerente. Per ripristinare uno stato coerente usare {@link #restore()}
	 */
	public void partialMove(SingleMove singMove) throws BadMoveException {
		if (!silent) System.out.println("Esecuzione mossa parziale: " + singMove);
		// eseguo le mosse: modifico la struttura dati
		// muovo fuori la posizione iniziale e dentro quella finale


		int startPos= singMove.getStartingPosition();
		int dice= singMove.getDice();

		int dest= calculateEndingPosition(startPos, dice);
		boolean hit= singleMove(startPos, dice);
		singMove.setHit(hit);

		if (dest!=singMove.getEndingPosition()) {
			throw new BadMoveException(singMove, "La posizione finale in SingleMove non e' corretta: sarebbe dovuta essere "+dest+" ma invece e' "+singMove.getEndingPosition());
		}

	}
	
	/**
	 * Se la mossa passata come parametro non e' corretta non viene modificata
	 * in alcun modo la struttura dati. Se la mossa e' corretta vengono
	 * annullati gli effetti di ogni chiamata a {@link #partialMove(CheckerMove)}
	 * (di fatto utilizzando il metodo {@link #restore()}) ed viene eseguita la 
	 * mossa modificando la struttura dati. Inoltre il nuovo stato che si viene
	 * a creare diventa il nuovo punto di ripristino.
	 * <p>
	 * Nota che non viene cambiato il turno del giocatore!
	 * <p>
	 * Inoltre modifica {@code move} impostando correttamente i flag hit
	 * @param move l'insieme di mosse effettuate dal player
	 * @return true se il giocatore che ha fatto la mossa ha vinto, false se la partita continua.
	 * @throws BadMoveException se la mossa non e' corretta.
	 */
	public boolean move(Move move) throws BadMoveException{
		
		// mossa corretta?
		checkMoveExc(move);
		// si', e' corretta
		
		restore();
		
		// sappiamo gia' il colore del player che sta muovendo grazie alla 
		// variabile turn (che e' uguale a move.getColor())
		
		try {
			if (!silent) System.out.println("Esecuzione della mossa: "+move);
			
			
			//if (!silent) System.out.println("> > >-------------------------------------");
			//if (!silent) System.out.println("Stato attuale:");
			//if (!silent) System.out.println(this.toString());
			move.clearHit();
			forceMove(move);
			
			//if (!silent) System.out.println("Nuovo stato:");
			//if (!silent) System.out.println(this.toString());
			//if (!silent) System.out.println("< < <-------------------------------------");
			
			
			if (!silent) System.out.println("Checker " + CheckerColor.BLACK + " sulla bar: " + getBarCheckers(CheckerColor.BLACK));
			if (!silent) System.out.println("Checker " + CheckerColor.WHITE + " sulla bar: " + getBarCheckers(CheckerColor.WHITE));
			
			if (!silent) System.out.println("Checker " + CheckerColor.BLACK + " usciti (bear off): " + getBorneOffCheckers(CheckerColor.BLACK));
			if (!silent) System.out.println("Checker " + CheckerColor.WHITE + " usciti (bear off): " + getBorneOffCheckers(CheckerColor.WHITE));
			
			// aggiorno lo stato stabile alla nuova situazione
			stableState= null; // elimino lo stato stabile precedente
			stableState= (Backgammon) this.clone();
			
		} catch (BadMoveException e) {
			throw new BackgammonError(this, "Eccezione durante l'esecuzione della mossa sebbene fosse stata validata", e);
		}
		
		
		// il giocatore ha vinto?
		
		if(getBorneOffCheckers(turn)==NUM_CHECKERS){
			//giocatore ha vinto
			if (!silent) System.out.println(turn + " ha vinto!!!");
			return true;
		} else {
			// la partita continua
			return false;
		}
		
	}

	/**
	 * Forza l'esecuzione di una mossa (modificando la struttura dati) senza 
	 * alcun controllo preventivo.
	 * <p>
	 * Inoltre modifica {@code move} impostando correttamente i flag hit
	 * @param move mossa da eseguire
	 * @throws BadMoveException mossa non legale (nota che la struttura dati potrebbe essere stata comununque modificata)
	 */
	private void forceMove(Move move) throws BadMoveException {
		if (move.getUsedDices().size()>4) {
			throw new BadMoveException(move, "Troppe mosse");
		}
		// eseguo le mosse: modifico la struttura dati
		// muovo fuori la posizione iniziale e dentro quella finale
		for (SingleMove sing : move) {
				
			int startPos= sing.getStartingPosition();
			int dice= sing.getDice();

			int dest= calculateEndingPosition(startPos, dice);
			boolean hit= singleMove(startPos, dice);
			sing.setHit(hit);

			if (dest!=sing.getEndingPosition()) {
				throw new BadMoveException(move, "La posizione finale in "+sing+" non e' corretta: sarebbe dovuta essere "+dest+" ma invece e' "+sing.getEndingPosition());
			}
		}

	}
	
	/**
	 * Verifica se una mossa e' legale.
	 * @param move l'insieme di mosse effettuate dal player
	 * @return true se la mossa e' legale, false altrimenti
	 */
	public boolean checkMove(Move move) {
		try {
			checkMoveExc(move);
			return true;
		} catch (BadMoveException e) {
			return false;
		}
	}
	
	/**
	 * Verifica se una mossa e' legale. Verifica anche se la mossa viene eseeguita
	 * dal giocatore che ha il turno
	 * <p>
	 * XXX Nota che al momento non e' implementata la regola descritta qui: 
	 * http://www.backgammon.it/regole/#movement ("Il movimento delle pedine", 
	 * ultimo punto)
	 * @param move l'insieme di mosse effettuate dal player
	 * @throws BadMoveException se la mossa non e' corretta.
	 */
	private void checkMoveExc(Move move) throws BadMoveException {
		if (!turn.equals(move.getColor())) {
			throw new BadMoveException(move, "E' il turno di "+turn+" ma la mossa e di "+move.getColor());
		}
		
		/*
		 * Ricorda che noLegalPositions(move) effettua una "simulazione" delle
		 * mosse passate come parametro, eventualmente sollevando un'eccezione
		 * se la mossa non e' valida. Dopodiche' restituisce true/false
		 * se esisono ulteriori mosse legali.
		 */
		// sono rimaste mosse fa fare?
		if (! noLegalPositions(move)) {
			// ne sono rimaste
			throw new BadMoveException(move, "Sono rimaste mosse da fare");
		} // else non ne sono rimaste
	}
	
	
	/// METODI PER OTTENERE LO STATO DELLA TAVOLA
	
	/**
	 * Ottiene un point
	 * @param position posizione nell'intervallo [1-24]
	 * @return point corrispondente alla posizione data
	 */
	public Point getPoint(int position) {
		return board[position-1];
	}

	/**
	 * Ottiene il numero di checker sulla bar
	 * @param color colore di cui si vuole ottenere il numero di checker
	 * @return
	 */
	public int getBarCheckers(CheckerColor color) {
		if (color.equals(CheckerColor.BLACK)) return barCheckersBlack;
		else return barCheckersWhite;
	}
	

	/**
	 * Ottiene il numero di checker usciti dalla tavola
	 * @param color colore di cui si vuole ottenere il numero di checker
	 * @return
	 */
	public int getBorneOffCheckers(CheckerColor color) {
		if (color.equals(CheckerColor.BLACK)) return borneOffCheckersBlack;
		else return borneOffCheckersWhite;
	}
	
	/**
	 * Ritorna il colore di chi ha il turno o null se non e' stato ancora stato eseguito lo spareggio
	 * @return vedi descrizione
	 */
	public CheckerColor whoseTurnIsIt(){
		
		return turn;
	}
	
	/**
	 * Restituisce un player
	 * @param color colore del player da restituire
	 * @return
	 */
	public Player getPlayer(CheckerColor color) {
		if (color.isBlack()) return blackPlayer;
		else return whitePlayer;
	}
	
	/**
	 * Restituisce il player nero
	 * @return
	 */
	public Player getBlackPlayer() {
		return getPlayer(CheckerColor.BLACK);
	}
	/**
	 * Restituisce il player bianco
	 * @return
	 */
	public Player getWhitePlayer() {
		return getPlayer(CheckerColor.WHITE);
	}
	
	//METODI PER SETTARE LO STATO DELLA TAVOLA
	
	/**
	 * Imposta il colore del player che ha il PRIMO turno
	 * @param color il colore del player che ha il turno
	 */
	public void setPlayerTurn(CheckerColor color){
		if (turn==null) {
			turn=color;
			stableState.turn= color;
			turnNum= 1;
			firstTurn= color;
			
			// inizialmente sono in un nodo CHANCE
			nodeType= BoardType.CHANCE;
			stableState.nodeType= BoardType.CHANCE;
		
			if (!silent) System.out.println(); // spazio bianco
			if (!silent) System.out.println("Turno #"+turnNum);
			if (!silent) System.out.println("Il player iniziale e': " + turn);

			if (!silent) System.out.println("Checker " + CheckerColor.BLACK + " sulla bar: " + getBarCheckers(CheckerColor.BLACK));
			if (!silent) System.out.println("Checker " + CheckerColor.WHITE + " sulla bar: " + getBarCheckers(CheckerColor.WHITE));
			
			if (!silent) System.out.println("Checker " + CheckerColor.BLACK + " usciti (bear off): " + getBorneOffCheckers(CheckerColor.BLACK));
			if (!silent) System.out.println("Checker " + CheckerColor.WHITE + " usciti (bear off): " + getBorneOffCheckers(CheckerColor.WHITE));
			
		} else {
			throw new BackgammonError(this, "Turno iniziale gia' impostato");
		}
	}
	
	/**
	 * Cambia il giocatore che ha il turno
	 * @return colore del nuovo giocatore che ha il turno 
	 */
	public CheckerColor tooglePlayerTurn(){
		if (turn.equals(CheckerColor.BLACK)) turn=CheckerColor.WHITE;
		else turn=CheckerColor.BLACK;
		
		if (turn.equals(firstTurn)) turnNum++;
		
		nodeType= BoardType.CHANCE; // dopo che uno a finito il turno, bisogna tirare i dadi
		
		stableState.turn= turn;
		stableState.nodeType= BoardType.CHANCE;
		
		if (!silent) System.out.println(); // spazio bianco
		if (!silent) System.out.println("Turno #"+turnNum);
		if (!silent) System.out.println("Ora e' il turno del player " + turn);
		
		return turn;
	}
	
	/**
	 * Restituisce il numero del turno
	 * @return
	 */
	public int getTurnNum() {
		return turnNum;
	}
	/**
	 * Restituisce il player che ha questo turno
	 * @return
	 */
	public Player getTurnPlayer() {
		if (turn.isBlack()) return blackPlayer;
		else return whitePlayer;
	}
	
	
	
	/// ALTRI METODI
	
	/**
	 * Lancia un singolo dado.
	 * <p>
	 * Ottieni un numero casuale tra 1 e 6 (estremi compresi)
	 */
	public int rollDice(){
		int val= Math.round((float)rand.nextFloat()*5+1);
		
		//val= rollDetDice(); // XXX ricordati di togliermi
		//val= rollDiceNoDouble(); // XXX ricordati di togliermi
		
		return val;
	}
	
	
	//private static int []dices= {1,6 , 2,3};
	private static int []dices= {1,6 , 2,2};
	private static int dicesIndex=0;
	/** Dado deterministico */
	private static int rollDetDice() {
		int val= dices[dicesIndex];
		dicesIndex++;
		if (dicesIndex>=dices.length) dicesIndex= 0;
		return val;		
	}
	private static int prevDice=1;
	// evita i dadi doppi
	private static int rollDiceNoDouble() {
		int val;
		do {
			val= Math.round((float)Math.random()*5+1);
		} while (val==prevDice);
		prevDice= val;
		return val;
	}
	
	
	/**
	 * restituisce true se 1<=dice<=6
	 * @param dice
	 * @return
	 */
	public static boolean checkDice(int dice) {
		if (1<=dice && dice<=6) {
			return true;
		} else {
			return false;
		}
	}
	
	/**
	 * Restituisce (checkDice(dice1) && checkDice(dice2))
	 * @param dice1
	 * @param dice2
	 * @return
	 */
	public static boolean checkDice(int dice1, int dice2) {
		return (checkDice(dice1) && checkDice(dice2));
	}

	/**
	 * Iteratore dei point della tavola
	 */
	@Override
	public Iterator<Point> iterator() {
		return new Iterator<Point>() {
			int index=0;
			
			@Override
			public boolean hasNext() {
				return (index<board.length);
			}

			@Override
			public Point next() {
				if (hasNext()) {
					Point p= board[index];
					index++;
					return p;
				} else {
					throw new NoSuchElementException();
				}
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
	}
	
	/**
	 * Nota che clono anche lo stato stabile
	 */
	@Override
	public Object clone() {
		try {

			Backgammon bg = (Backgammon) super.clone();
			
			// l'unica cosa da fare e' clonare la boardd
			bg.board= new Point[board.length];
			for (int k=0; k<board.length; k++) {
				bg.board[k]= (Point) board[k].clone();
			}
			
			if (stableState!=null) {
				bg.stableState= (Backgammon) stableState.clone();
			}
			return bg;
			
		} catch (CloneNotSupportedException e) {
			// non accadra' mai
			throw new InternalError("Come puo' essere CloneNotSupportedException?");
		}
	}
	
	@Override
	public String toString() {
		String str="< #" + turnNum + "-" + turn + " >";
		return str;
	}
	
	public String fullStateToString() {
		String str="";
		
		str+= "Giocatore con il primo turno: " + firstTurn + "\n";
		str+= "Turno #" + turnNum + " - " + turn + "\n";
		str+= CheckerColor.BLACK + " sulla bar: " + getBarCheckers(CheckerColor.BLACK) + "\n";
		str+= CheckerColor.WHITE + " sulla bar: " + getBarCheckers(CheckerColor.WHITE) + "\n";
		str+= CheckerColor.BLACK + " fuori: " + getBorneOffCheckers(CheckerColor.BLACK) + "\n";
		str+= CheckerColor.WHITE + " fuori: " + getBorneOffCheckers(CheckerColor.WHITE) + "\n";
		
		for (Point p : this) {
			str+= p.toString() + "\n";
		}
		
		return str;
	}
	
	/**
	 * Quando e' impostato come "silente", non stampa su stdout
	 * @param silent
	 */
	public void setSilent(boolean silent) {
		this.silent= silent;
		//if (silent) System.out.println("silent=true; => inizio esplorazione albero");
		//else System.out.println("silent=false; => fine esplorazione albero");
	}

	/**
	 * Quando e' impostato come "silente", non stampa su stdout
	 */
	public boolean isSilent() {
		return silent;
	}

	/**
	 * Restituisce il colore del vincitore o {@code null} se la partita non e'
	 * finita
	 * @return
	 */
	public CheckerColor winnerColor() {
		if (getBorneOffCheckers(CheckerColor.BLACK)==NUM_CHECKERS) {
			return CheckerColor.BLACK;
		} else if (getBorneOffCheckers(CheckerColor.WHITE)==NUM_CHECKERS) {
			return CheckerColor.WHITE;
		} else {
			return null;
		}
	}
	
	// METODI CHE IMPLEMENTANO L'INTERFACCIA Board
	
	public void setRoll(int dice1, int dice2) {
		if (!nodeType.equals(BoardType.CHANCE)) {
			throw new BackgammonError(this, "Il nodo attuale e' di tipo "+nodeType+" ma sarebbe dovuto essere "+BoardType.CHANCE);
		}
		
		roll= new Roll(dice1, dice2);
		// vado in un nodo MIN o MAX
		nodeType= BoardType.color2type(turn);
		stableState.nodeType= BoardType.color2type(turn);
		
		
		/* XXX
		if (!silent) {
			List<? extends MoveEvent> allMoves = moveEvents();
			System.out.println("Possibili mosse ("+allMoves.size()+")");
			for (MoveEvent move : allMoves) {
				Move m= (Move) move;
				System.out.println("\t" + m + " \t; dadi usati("+m.getUsedDices().size()+"): " + m.getUsedDices());
				if (m.getUsedDices().size()>4) {
					System.err.println("troppe mosse");
				}
			}
		}
		*/
	}
	
	@Override
	public boolean isTerminal() {
		// restituisco true se qualcuno ha vinto
		if (
			getBorneOffCheckers(CheckerColor.BLACK)==NUM_CHECKERS ||
			getBorneOffCheckers(CheckerColor.WHITE)==NUM_CHECKERS ) {
			return true;
		} else {
			return false;
		}
	}

	@Override
	public List<? extends ChanceEvent> chanceEvents() {
		List<Roll> list= Roll.allRolls();
		// Collections.shuffle(list, rand); // XXX sembra che non porti a miglioramenti e forse li peggiora
		return list;
	}

	@Override
	public Board successor(ChanceEvent e) {
		// restituisco lo stato successivo senza modificare lo stato attuale
		
		if (nodeType!=BoardType.CHANCE) {
			throw new BackgammonError(this, "Il nodo attuale e' di tipo "+nodeType+" ma sarebbe dovuto essere "+BoardType.CHANCE);
		}
		
		if (e instanceof Roll) {
			
			Backgammon clone= (Backgammon) clone();
			Roll r= (Roll) e;
			clone.setRoll(r.getHighDice(), r.getLowDice());
			return clone;
			
		} else {
			throw new ClassCastException();
		}
	}

	@Override
	public List<? extends MoveEvent> moveEvents(Evaluator eval) {
		
		if (nodeType==BoardType.CHANCE) {
			throw new BackgammonError(this, "Il nodo attuale e' di tipo "+nodeType+" ma sarebbe dovuto essere "+BoardType.MAX+" oppure "+BoardType.MIN);
		}
		
		// moveEvents() restituisce un set
		Set<Move> allMovesSet;
		duplicati= 0;
		allMovesSet= moveEvents(new LinkedHashSet<Move>(), new LinkedHashSet<Move>(), new Move(roll.getHighDice(), roll.getLowDice(), turn));
		if (duplicati>0) throw new BackgammonError(this, "Duplicati: "+duplicati);
		
		// ordino le mosse
		LinkedList<Entry<Double, Move> > sortedMoves= new LinkedList<Entry<Double, Move> >();
		boolean isBlack= false;
		for (Move m : allMovesSet) {
			
			// calcolo lo stato che si ottiene dopo aver eseguito la mossa
			Backgammon bgClone= (Backgammon) stableState.clone();
			try {
				bgClone.forceMove(m);
			} catch (BadMoveException e) {
				// errore fatale
				throw new BackgammonError(this, "Errore eseguendo una mossa restituita da moveEvents()", e);
			}
			
			// calcolo l'euristica (score) del nuovo stato
			double score;
			if (m.getColor().isWhite()) {
				score= eval.evaluate(bgClone, false);
				isBlack= false;
			} else {
				score= eval.evaluate(bgClone, true);
				isBlack= true;
			}
			
			// ordino la mossa in base allo score
			sortedMoves.add(new AbstractMap.SimpleEntry<Double, Move>(score, m));
		}
		
		// trasformo il set in una lista
		LinkedList<Move> listMoves= new LinkedList<Move>();
		
		if (isBlack) {
			// ordinamento decrescente
			Collections.sort(sortedMoves, new Comparator<Entry<Double, Move>>() {
				@Override
				public int compare(Entry<Double, Move> o1,
						Entry<Double, Move> o2) {
					return o2.getKey().compareTo(o1.getKey());
				}
			} );
		} else {
			// ordinamento crescente
			Collections.sort(sortedMoves, new Comparator<Entry<Double, Move>>() {
				@Override
				public int compare(Entry<Double, Move> o1,
						Entry<Double, Move> o2) {
					return o1.getKey().compareTo(o2.getKey());
				}
			} );	
		}
		for (Entry<Double, Move> e : sortedMoves) {
			listMoves.add(e.getValue());
		}
		
		
		// restituisco una lista ordinata
		return listMoves;
	}
	
	static int duplicati= 0;
	/**
	 * 
	 * @param allMoves mosse complete, ovvero che hanno utilizzato tutti i dadi
	 * @param partialMoves mosse non complete
	 * @param moves la mossa eseguita finora
	 * @return
	 */
	private Set<Move> moveEvents(Set<Move> allMoves, Set<Move> partialMoves, Move moves) {
		
		// dadi ancora da usare
		List<Integer> dices= new LinkedList<Integer>();
		dices.addAll( expandDices(moves.getHighDice(), moves.getLowDice()) );
		for (Integer i : moves.getUsedDices()) {
			dices.remove(i);
		}

		if (dices.isEmpty()) {
			/*
			 * TODO in questo punto potresti gia' calcolare l'euristica per l'ordinamento delle mosse.
			 * In realta' dovresti farlo nel passo precedente, quando e' ancora presente
			 * lo stato che si ottiene dopo aver effettuato questa mossa
			 */
			
			// fine ricorsione
			if (!allMoves.add(moves)) duplicati++;
			return allMoves;
		}
		
		int []positions= new int[25];
		positions[0]= BAR;
		for (int k=1; k<25; k++) {
			if (moves.getColor().isBlack()) positions[k]= k;
			else positions[k]= 25-k;
		}
		
		boolean noLegalPositions= true;
		
		for (int startPos: positions) {

			if (!checkStartingPosition(startPos)) {
				// non posso muovere partendo da qui
				continue;
			}
			
			for (Integer d : dices) {

				try {

					Backgammon bg= (Backgammon) this.clone();
					int endPos= bg.calculateEndingPosition(startPos, d);
					boolean hit= bg.singleMove(startPos, d);
					
					/*
					 * TODO potrebbero generarsi mosse duplicate se non si considera il flag hit
					 * 
					    Queste due mosse sono da considerare uguali (cambia solo l'ordine)
						1-4 4-6
						1-3 3-6
						
						Queste due mosse sono da considerare diverse
						1-4* 4-6
						1-3 3-6

					 * Potresti fare in questo modo: considerare l'insieme delle
					 * coppie (point partenza, point arrivo) senza considerare 
					 * gli hit e l'array dei point su cui e' stato fatto hit.
					 * Entrambi set non ordinati. Due mosse sono uguali se 
					 * questi due set set sono uguali.
					 */
					SingleMove sm= new SingleMove(startPos, endPos, d, moves.getColor());

					Move mvcl= (Move) moves.clone();
					mvcl.add(sm);
					noLegalPositions= false;
					
					if (partialMoves.add(mvcl)) {
						// mvcl non era contenuto in partialMoves
						bg.moveEvents(allMoves, partialMoves, mvcl); // ricorsione
					}

					

				} catch (BadMoveException e) {
					// la mossa non era valida, provo con il prossimo dado
				}

			}
			
		}
		
		if (noLegalPositions) {
			// non ho mai fatto la ricorsione
			// non ho trovato alcuna posizione legale
			// aggiungo ugualmente questa mossa
			
			if (!allMoves.add(moves)) duplicati++;
		}
		
		return allMoves;
	}
	
	@Override
	public Board successor(MoveEvent e) {
		// restituisco lo stato successivo senza modificare lo stato attuale

		if (nodeType==BoardType.CHANCE) {
			throw new BackgammonError(this, "Il nodo attuale e' di tipo "+nodeType+" ma sarebbe dovuto essere "+BoardType.MAX+" oppure "+BoardType.MIN);
		}

		if (e instanceof Move) {

			try {
				
				Backgammon clone= (Backgammon) clone();
				clone.move((Move)e);
				clone.tooglePlayerTurn();
				return clone;
				
			} catch (BadMoveException e1) {
				// salvo bug, non capitera' mai
				throw new BackgammonError(this, "Errore nel calcolo del successore. La mossa e' " + e, e1);
			}
			
		} else {
			throw new ClassCastException();
		}
	}

	@Override
	public BoardType getBoardType() {
		return nodeType;
	}


}
